package com.leetcode.easy;

/**
 * @Classname SolutionClimbStairs
 * @Description 爬楼梯
 * @Date 2020/8/25 15:36
 * @Created by zfl
 */
public class SolutionClimbStairs {
    /*
    *@Description 分析规律可以看出爬上x层的次数 = 爬上x - 1层的次数 + 爬上x - 2层的次数
    *@param [n]
    *@return int
    * 运行时间太长
    */
    public int climbStairs1(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;
        return climbStairs1(n - 1) + climbStairs1(n - 2);
    }
    /*
    *@Description 动态规划
    *@param [n]
    *@return int
    * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
    * 内存消耗：36.6 MB, 在所有 Java 提交中击败了11.38%的用户
    */
    public int climbStairs2(int n) {
        int p = 0, q = 0, r = 1;
        for(int i = 1; i <= n; ++i) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }
}
